import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 21:16
 * @description SPFA 算法 使用 队列来优化 Bellman-Ford
 * 在松弛操作中，只有上一次被松弛的点，所连接的边，才有可能引起下一次松弛操作
 * 因此用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。
 * SPFA 也可以用于判断 s 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 s点可以抵达一个负环。
 */
public class Solution {
    /**
     * 存储图
     */
    List<int[]>[] graph;
    /**
     * 存储源点到其他点的最短路
     */
    int[] dis;

    /**
     * 判断点是否访问过
     */
    boolean[] vis;
    /**
     * 正无穷
     */
    int INF = Integer.MAX_VALUE / 2;

    /**
     * 求最短路并判断通过s能够到达一个负环
     * @param n n个结点，编号 0..n-1
     * @param s 源点s
     * @param edges u e[0] v e[1] w(u,v) = e[2]
     * @return 是否存在负环
     */
    public boolean sPFA(int n, int s, int[][] edges) {
        // 1. 初始化邻接表
        graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e: edges) {
            graph[e[0]].add(new int[]{e[1], e[2]});
        }
        // 2. 初始化源点s 到 其他点的最短路
        Arrays.fill(dis, INF);
        dis[s] = 0;

        // 3. 初始化访问标志
        vis = new boolean[n];
        vis[s] = true;

        // 4. 记录最短路经过的边数
        int[] cnt = new int[n];

        // 5. 队列维护发生松弛操作的点
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            vis[u] = false;
            for (int[] e: graph[u]) {
                int v = e[0], w = e[1];
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    cnt[v] = cnt[u] + 1;
                    // 在不经过负环的情况下，最短路至多经过 n - 1 条边
                    // 因此如果经过了多于 n 条边，一定说明经过了负环
                    if (cnt[v] >= n) {
                        return false;
                    }
                    if (!vis[v]) {
                        q.add(v);
                        vis[v] = true;
                    }
                }
            }
        }
        return true;
    }
}
